/*
练习5-4 转换树的表示法
分数 25
作者 陈越
单位 浙江大学

父亲表示法是树最简单、空间效率最高的存储结构。请设计将基于父亲表示法的树转换为孩子兄弟表示法，即二叉链表结构的树的算法。在此规定任一结点的子结点按索引编号的递增序从头向尾链接。
函数接口定义：

BinaryTree ConvertTree(Tree tree, int n);

其中 BinaryTree 数据类型的定义如下：

typedef int TElemSet;
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;             // 数据元素 
    BinaryTree first_child;    // 第一个子结点 
    BinaryTree next_sibling;   // 下一个兄弟结点 
};

父亲表示法下 Tree 数据类型的定义如下：

typedef int Position;
#define NIL -1
typedef struct TreeNode *Tree;
struct TreeNode {
    TElemSet data;    // 数据元素 
    Position parent;  // 父结点位置 
};

函数 ConvertTree 的功能是：将父亲表示法存储的、有 n 个 Tree 类型结点的数组 tree 转化为 BinaryTree 类型的二叉链表结构的树，并返回指向根结点的指针。在 tree 中，根结点的 parent 值为 NIL。
注意：返回的树中，兄弟链表必须按兄弟结点索引编号（即数组下标）的递增序从头向尾链接。

输入样例：

9
10 3
15 2
23 3
12 -1
19 3
32 2
43 2
60 5
51 2

输出样例：

12
10
23
15
32
60
43
51
19
*/

#include <stdio.h>
#include <stdlib.h>

/* 孩子兄弟表示法结构定义 */
typedef int TElemSet;
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;             /* 数据元素 */
    BinaryTree first_child;    /* 第一个子结点 */
    BinaryTree next_sibling;   /* 下一个兄弟结点 */
};
/* 孩子兄弟表示法结构定义 结束 */

/* 父亲表示法结构定义 */
typedef int Position;
#define NIL -1
typedef struct TreeNode *Tree;
struct TreeNode {
    TElemSet data;    /* 数据元素 */
    Position parent;  /* 父结点位置 */
};
/* 父亲表示法结构定义 结束 */

BinaryTree ConvertTree(Tree tree, int n);

void Visit(BinaryTree tree)
{
    printf("%d\n", tree->data);
}

void PreOrder(BinaryTree tree)
{
    if (tree != NULL) { /* 空树不做处理，直接返回 */
        Visit(tree);                  /* 先访问结点tree */
        PreOrder(tree->first_child);  /* 接下来访问tree所有子孙结点 */
        PreOrder(tree->next_sibling); /* 最后访问tree后序的兄弟结点及其子孙 */
    }
}

int main(void)
{
    int n, i;
    Tree tree;
    BinaryTree bin_tree;
    
    scanf("%d", &n);
    tree = (Tree)malloc(sizeof(struct TreeNode) * n);
    for (i=0; i<n; i++) {
        scanf("%d %d", &tree[i].data, &tree[i].parent);
    }
    bin_tree = ConvertTree(tree, n);
    PreOrder(bin_tree);
    
    return 0;
}
/* 你的代码将被嵌在这里 */

BinaryTree ConvertTree(Tree tree, int n) {
    if (n <= 0) return NULL;

    BinaryTree root = NULL;
    // 创建一个数组来存储每个节点对应的 BinaryTreeNode 指针
    BinaryTree *nodes = (BinaryTree *)malloc(n * sizeof(BinaryTree));
    for (int i = 0; i < n; i++) {
        nodes[i] = (BinaryTree)malloc(sizeof(struct BinaryTreeNode));
        nodes[i]->data = tree[i].data;
        nodes[i]->first_child = NULL;
        nodes[i]->next_sibling = NULL;
        if (tree[i].parent == NIL) {
            root = nodes[i];
        }
    }

    // 遍历每个节点，建立父子关系
    for (int i = 0; i < n; i++) {
        Position parent = tree[i].parent;
        if (parent != NIL) {
            // 将当前节点链接到其父节点的子节点链表中
            BinaryTree parentNode = nodes[parent];
            if (parentNode->first_child == NULL) {
                // 如果父节点还没有子节点，直接链接为第一个子节点
                parentNode->first_child = nodes[i];
            } else {
                // 否则，找到父节点的最后一个子节点，将当前节点链接为它的兄弟
                BinaryTree sibling = parentNode->first_child;
                while (sibling->next_sibling != NULL) {
                    sibling = sibling->next_sibling;
                }
                sibling->next_sibling = nodes[i];
            }
        }
    }

    free(nodes);
    return root;
}